1. Field of the Invention
The present invention relates to a data processing unit, more specifically to a problem solving apparatus for processing symbols, and provides a learning function for the problem solving apparatus.
2. Description of the Related Art
In the field of artificial intelligence, most problem solving methods being developed are based on a trial-and-error search concept. That is, a problem is solved by searching for one solution in a space where the solution can exist. The present invention is based on a problem solving apparatus operated by a tree searching method in the symbol process.
The tree searching method in the symbol process is described below by referring to a simple example.
FIGS. 1A and 1B show an 8-tile puzzle. In this puzzle, there is an empty space of one frame and eight numbered tiles which are freely movable in the up, down, right, and left directions in a 3.times.3-block frame. When one of the numbered tiles above, below, right, and left of the space is moved into the space, the previous position of the moved number tile becomes the space. In other words, when the number tile is moved, the space appears to have moved.
In the 8-tile puzzle, a problem is that, for example, a starting pattern as shown in FIG. 1A is to be converted into a goal pattern as shown in FIG. 1B. Assuming that moving the space once is regarded as one step, a solution is obtained by tracing a path to the goal pattern shown in FIG. 1B in the smallest possible number of steps.
FIG. 2 shows an example of the result of the tree searching process to solve the problem shown in FIGS. 1A and 1B.
In the tree structure, one state of the arrangement of the numbered tiles in the 8-tile puzzle is referred to as a "node". That is, FIG. 1A shows the arrangement at a starting node, FIG. 1B shows the arrangement at a goal node. In the tree structure, each node has only one parent node except the starting node, which is a specific node having no parent node.
In the tree search, the efficiency of the searching process is greatly affected by the order from the starting node to the child nodes, that is, by how the nodes are expanded.
The order can be determined by, for example, a breadth-first method, a depth-first method, etc.
FIG. 2 shows a result of the breadth-first method. In the breadth-first method, nodes are sequentially expanded in the order in which the nodes were generated. In FIG. 2, the three child nodes 2, 3, and 4 are generated from the starting node 1. That is, the nodes are first generated in the horizontal direction by priority, and the nodes in the first row (depth 1), second row (depth 2), . . . are generated in this order.
On the other hand, the last generated node is first expanded in the depth-first method. That is, nodes are generated in the order from the starting node 1 to nodes 2, 5, 10, 20, 11, 21, . . . That is, the nodes are expanded in the vertical direction by priority.
In FIG. 2, the goal node is obtained as a child node to node 26, and the solution path to the problem shown in FIGS. 1A and 1B in the 8-tile puzzle is indicated by bold lines. By moving the space 5 times (in 5 steps), the starting pattern (FIG. 1A) is converted into the goal pattern (FIG. 1B), and the goal node cannot be reached with a smaller number of times of moving the space.
FIG. 3 is a block diagram showing the configuration of the conventional problem solving apparatus operated in a symbol process.
In FIG. 3, a problem is generated by a problem generating apparatus 101, and the generated problem is provided for the problem solving apparatus 100.
The problem solving apparatus 100 performs the problem solving process as shown in FIG. 2 until a solution can be obtained through a tree search, and comprises a node expanding apparatus 102 and a node evaluating apparatus 103.
The node expanding apparatus 102 generates a child node from a parent node, that is, it expands nodes.
The node evaluating apparatus 103 evaluates the node expanded by the node expanding apparatus 102 as to whether or not the node refers to a goal node.
The processes of the node expanding apparatus 102 and node evaluating apparatus 103 are repeated until the solution is successfully obtained.
However, if a random searching method is followed by either the depth-first method or breadth-first method in the tree search, then the process of detecting a path to the goal node refers to a wasteful process. When the number of nodes expanded before the optimum path is detected is too large, a considerably long time and a large amount of stored information are spent on the search.
Conventionally, a solution can be obtained in a reduced search space and in a reasonable time by introducing information indicating the rule of thumb, that is, information referred to as heuristic knowledge. The word "heuristic" means "serving to discover". The heuristic information is used to help a goal node be reached in the search by extending the most probable node first from experience.
In using the above described method, it is necessary for a user to appropriately detect the required heuristic knowledge and provide it to a problem solving apparatus, involving a great expenditure of labor and time.
Furthermore, in solving a problem already solved, the conventional problem solving apparatus again requires the process time spent in practically solving the problem first. That is, a problem similar to a problem solved already, requires the same process time, without shortening it.